#include <bits/stdc++.h>
#include "caltime.cpp"
#include "read_data.cpp"
using namespace std;

// solving 
int best_ans;
int dp[30][10001];
int ans[30];
void dp_solve(){
	for(int i=0;i<=c;i++)dp[0][c]=0;
	for(int i=1;i<=n;i++){
		dp[i][0]=0;
		for(int j=1;j<=c;j++){
			dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
			if(j>=bag[i-1].w)dp[i][j]=max(dp[i][j],dp[i-1][j-bag[i-1].w]+bag[i-1].v);
		}
	}
	int j=c;
	for(int i=n;i;i--){
		if(dp[i][j]==dp[i-1][j])ans[i-1]=0;
		else ans[i-1]=1,j-=bag[i-1].w;
	}
	best_ans=dp[n][c];
}

void solve(int k){
	double T=0;
	for(int i=0;i<100;i++){
		Start();
        dp_solve();
		End();
		T+=Cal_it();
	}
	printf("data#%d :\n",k);
	printf("n: %d  c: %d \n",n,c);
	printf("answer : %d \n",best_ans);
	for(int i=0;i<n;i++)printf("%d",ans[i]);puts("");
	printf("Ave-Time: %.4lfms\n",T/100);puts("");
}

int main(){
	read_file_names();
	freopen("dynamic_programming","w",stdout);
	for(int i=0;i<N;i++){
		read_data(i);
		solve(i); 
	}
}

